package pers.sloera.leetcode.editor.cn;

/**
 * 使字符串平衡的最少删除次数
 *
 * @author sloera
 * @date 2023-03-06 23:41:45
 */
class MinimumDeletionsToMakeStringBalanced {
    public static void main(String[] args) {
        Solution solution = new MinimumDeletionsToMakeStringBalanced().new Solution();
        // System.out.println(solution.minimumDeletions("aababbab"));
        System.out.println(solution.minimumDeletions(
                "baababbbaabaabaabbabbaabaabaaaabaabbbabbbaaabababaabbbbabbbbabaaabbabaaabbaaabaabbbbbaabbbbabbaaabaabaaaababaabbbaabaaabbabbbaabbbaaabbbabbaaabababaabbbababababbaaaabbababbaabbbabaaabbbbbbaaabaaaabbaaaaabaabbaabaaaaabbbabbbbaaaabbaaaababaaaabbbbaaabbbbbbaabbaabaaababababaababbaaaaabbabababbbbababababbbbbabababbaababbbaababbbaaababbbbaaabababbaabaaaaaabaababbaaabaabbabbabbbaabbbaababbaabbaaabbaabbaabaaababababbabbbabbbbbbaaabaaabaabbaabbabbbbabbbbbaaaaababbaabbaabaaaaaaabbbbababbaabbbabbabbbabaababbbbaababaabaaaababbabbabaababababbabbbbabbbbaaabaaabbabbabbaababbbbaabbababbababaabbbbaabbabaabababbbbabaaabbbaaabaabaaaabbaaabaababbbbaabbbbbaabbbbabaaaabbabbbaababbaabbbbbabababbaaaabbbbbbaabbaaaabaabbbbbbbbaaaabaaaabaaabbbbababaabababbbbabbbaabaaabbabbabaababbbabababbaaaaaaabbbabbbbaaaabbaaaababbabababbbabaabbaabaaabaabbaabbabbbbaabbbbbbaabbaabbaaaaababbaabaabaabaabbbabaabaaaaabababbbbbbbabbaabbabaabbabbbbbbabaabbbbbbbbabbbabbbbbabbbababaabbbabbbaabbbbbbaaabbbbaabaaabbbaaaababbbbaabaabbaaaababaabaaaabbaabbbbabababbbaaaaaaaaaabbbbabaababaaabaaaaaaabaabbabaabbaaabbababbabaabaaaaaaabaaabaabbbaaabaaabbbaaababaabaaabbabaabbaaaabbbbaabbaabbbbaabaababaabaaabababbabaabababbaabbbbbaabbbaabababbbbabbbbbaaaabbabababababbababaaaabaaababbbabaabaabbbbaabbbaaabbbbabaaaaaababbbabbbaaabbbbabaabaaaabbabbabbbaaabbbbabbbbbabaaaaabbabaaaabbaabbababbaaaabbabbabaabaabaababaabaabbaaabbabbabababbaaababbababbabbbaabbabaabbabbbbababbbaabaabbaabbabaabaababababbbbbbbbabbaaabababaaabbbbbaabbbbaaaaaabbbabaababaabbbbbaabababababaaaaabbbaaabaababbbbaabaaabbaaabbbaaaaaabbababbbaabaaaaaaaabbabaaaababbbbbaabababbbabbabaabbabababbbbbbaabbbaabbabbbbababbbbaaaaaabbbaababbaabababbbbabbababbbabaaabbbaaabbababbabbbbbbbbaababbbbaaaabbaabbbabaaaaabbbabbbbbaababbaabbbbaaabbbbababbabbbbbababbaaabbbbabaabbbbbababbbaaaababbbaabbbabbababaaababbaaaabbbababaaaaaaaaaaabbbbaaaaabaaabbbbbabababaabbbbaabaaabababaaabaabbbbaaabaaabbbaabbbbababbabaabbabaabbaaabbbbbbbabbaabbababbababaaaaabaabaaabbaaaaabbbabaaaabaabaabbaabbabbabaaaaaabbbbabbaababbababaaaabbbaaaabaaabaaabbaabaaababbabbaabbbbbbbbbbababababaabbababbababbbabaaaababbabaababbbabbabbbbaabbabbbabaabaaabbabbabbbbabaaababaabbabbbbabaabaabaaaababbabbabbbaaababbbaaaabaabbbbaababbbbabbaabaabbbbbabbaaabbbabbbaaaaabaabbbabbbbaabbaabbbbaaabbbabaabbababbabbababaabbbaababbbabbbbbabbaabbabaabbbbbbbabaabbbaaaaabbaabbabbbbbaabbaabbababbbbbaabaaaaaaaaaababbbaaaabbaaabbbbababbabaaabaabbabbaabbabbaabbababbaabbabaabbababaaabbbababbbbabbbabaaabbababbbbaabaaaabbababbbbbbbbababbaabaabbbabbaaaaaababbaaabbaaababaaababbabababaababbabaaabbbbbbbaabaaabaaababbabaabbbbaaaababbbbbababaaaabbbbbabbbbababbbbaaabbaaabbabbababababaaabaabaaabaabaaabbabaaabbabaaaaaaababbaabbababbbbabbbbaaaabaababbbababbbbaababababbbbabbbaabbaabbaaaaaaaabbbaaababbaaabaaababbbaaaaababaaabaabbaabababaababbaaabbabaabbbababaabbbbaababababababbabbabbabbbabaaabbbbbabbbbabaabaaaaabbbbabbbbbaabbbbaaaaaabbbaaabaabbababababaabababababbbbbabbababaabaaabbbbbabbbabbbbabbbbabbabababbabbbbabaaabaaaaabbaaababbbbaabaabbbaaabaabababbaaaaababaababbbaabbabbaabbabbabbaababaabababbbababbbababbaaaaaabaaababbaababaaaababbbbaaaaabbaabaaabaaaabbbababbaaababbaaabbabbbbbbaaababaabbbbbbabaaabbbabbbbbabbabbabababbbbabaaaabbaabbbaabbabbabbbabbbaaabababbaaaabababaabaabbbaaaaabaabbbaabbbabbaabaabbbabbaaabbbbbaaaaaabaaaaabbabbabaaababaabbabbbbabbbabaaabababbbaaabbbabbbbbbbaabaabbbaabaabbbaaaabbaabbbaababbbbabbaaaababaabbabaaaabbaabaaabbbbababaababaabababbbaaaabaaaababbabaabbbabbabbbbaaababbbababaabbaabababbaaabaaabbaaababbaabbaabbaabbbaaabbbaababbababbbabaababbabaabaababababaaaabbabaaababbbababbabaabaabbababaaabbbbaaaabbabababaabaaaabbababbababaaaaaabaaababbbaaaabaaabbbaaabbaaabbbbabbbbbbbbbababaaabbbbaabbbaaaaabaabbabbbbbbaababbaabbbbbbbabababaaabbabababbaababbabaababaaabbababaabaababaaaaaabaabbabbbbbbabbabaabbbbaaabbbababaabbbabbbababaabbbabbbbababbaabbbaabbbaabaabbbbbbbabaababaabababbaabababaaabaaabbaaaabbbbaababaabababbabbbaaaabbbababababbaabbabbaabbaabaababaababbbabaaaabbbaaaabbbaaabbbaaababaaabaababbabbaabababaaaaaaabbbababbabbabbbbabbabbaababbabbbabaaaaababaaaabbbbbbbaabbbbababbbbbbababaaabbbbbbaaaaaaaaababaabbaaabaaaaabababaabaaaabbbbbabaabbbaabaabbaababaabbbababbbbaaabaabbabbbaabaabbaabbababaaabaaaaabbbabaabbababbbaababaaaabaaaabbbbaabbabbaabbbbababababaaabbaaabaababbbbbaaabbbaabbaaaabbbbaaaabababababbaabbabbbaaaababaaaaaaaababaaaaaaabaababbaaaabbbaabbbbbbbbbaabbabbbaabbabaabababbbaaaaabbabbaabbababbbbbababababbbbbababbabbbabbabbabbabababbbaabbbaabbaababbbaabaabaaababaaaaabbbbbbabaaabbabbbaabaabaaaaabbbbbaababaaaaaabbbbbbabbababbabbaaabbaaaaabbabbbbaaabaaabaabbaababbbababbaaaaabbbbabaabbbbabaaabaabaababbababbaaaabaabbbababbbabaabbaababbabbbbababbbaaabbbaaaaaaaaaabaabbbbbaaaaababbbaaaabbaabbbaabaaababaabbaabbbbaabaabbbabaabaabbbbaaaabbaababbababbaaababaaaaaaababbbabbabbbaaaaaaababbbabaaaabaabbabaaaabbaabbbbbbbabbabaababbaaaabababaaaaaaabaaaabbabbbaaaaabaaabaaabbaaaabbbbaaaaaaababbbbbaaaaabbabababaabbbaababbaabbaababaaaabbbbaabbaaabbbbabbaaabbbabbababbbaabbbaaabbbaaaabaaabbababaabbbbaabaaabbaabbabbbaabaaaaaaaaaabbabbabaababaabaaaaabaabaaaaabbbaababaabaaabaaaababbbbababbbbabaaabbbabbbaabaabbabbbaaaabbaabbbababbaabaaaaababababbaaaababaababaaabbabbbaaaaaababbbbaabaaabbbbbaabbbbbaaaaabaaabaabaaaababbbaaaabbabbabaaabaaaabbaabbbaabbbbbaabababaababbabbaaaababaabbababbabbaabbabbbaabaabbabaabaabbaaabbabbababaabaabaabbaabbbbaaaaaaababababaabbaabbbbaabaaababbaabbabaaabaabaabbaababbbaaaaaaabaabaabbbaaabbababbbabbabaabbbabbaabaaabaabaaabaabbbabaaaaabaabbbbbaaabbabab"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * a必须在b前
         */
        public int minimumDeletions(String s) {
            int[] dpA = new int[s.length() + 1];
            int[] dpB = new int[s.length() + 1];
            // int maxB = (int) s.chars().filter(x -> x == 'a').count();
            // int maxA = s.length() - maxB;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i <= s.length(); i++) {
                int minA = minA(dpA, s, i);
                // 左边肯定比结果大，没有继续下去的必要了
                if (minA > min) {
                    break;
                }
                int minB = minB(dpB, s, i);
                min = Math.min(minA + minB, min);
            }
            return min;
        }

        private int minB(int[] dpB, String source, int i) {
            if (i == 0) {
                dpB[i] = (int) source.chars().filter(x -> x == 'a').count();
            } else {
                dpB[i] = dpB[i - 1] - (source.charAt(i - 1) == 'b' ? 0 : 1);
            }
            return dpB[i];
        }

        private int minA(int[] dpA, String source, int i) {
            if (i > 0) {
                dpA[i] = dpA[i - 1] + (source.charAt(i - 1) == 'a' ? 0 : 1);
            } else {
                dpA[0] = 0;
            }
            return dpA[i];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
